package 剑指offer;

/**
 * @author: tyy 剑指 Offer
 * 488. 祖玛游戏
 *你正在参与祖玛游戏的一个变种。
在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。
你的目标是 清空 桌面上所有的球。每一回合：
从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。
接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。
如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。
如果桌面上所有球都被移除，则认为你赢得本场游戏。
重复这个过程，直到你赢了游戏或者手中没有更多的球。
给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。
示例 1：
输入：board = "WRRBBW", hand = "RB"
输出：-1
解释：无法移除桌面上的所有球。可以得到的最好局面是：
- 插入一个 'R' ，使桌面变为 WRRRBBW 。WRRRBBW -> WBBW
- 插入一个 'B' ，使桌面变为 WBBBW 。WBBBW -> WW
桌面上还剩着球，没有其他球可以插入。
 * @create: 2021-10-31 17:40
 * @description:
 **/
public class Solution21 {
    int minStep = 0;
    int overStep = 0;

    public int findMinStep(String board, String hand) {
        int[] colorIndex = new int[25];
        colorIndex['R' - 'A'] = 0;
        colorIndex['Y' - 'A'] = 1;
        colorIndex['B' - 'A'] = 2;
        colorIndex['G' - 'A'] = 3;
        colorIndex['W' - 'A'] = 4;
        int[] handMap = new int[5];
        for (int i = 0; i < hand.length(); i++) {
            handMap[colorIndex[hand.charAt(i) - 'A']]++;
        }
        StringBuilder boardSb = new StringBuilder();
        for (int i = 0; i < board.length(); i++) {
            boardSb.append(colorIndex[board.charAt(i) - 'A']);
        }
        overStep = hand.length() + 1;
        minStep = overStep;
        dfsMinStep(boardSb, handMap, 0);
        return minStep == overStep ? -1 : minStep;
    }

    private void dfsMinStep(StringBuilder boardSb, int[] handMap, int step) {
        compress(boardSb);
        if (boardSb.length() == 0) {
            minStep = Math.min(minStep, step);
        }

        if (step >= overStep) {
            return;
        }

        int i = 0;
        int j = 1;
        while (i < boardSb.length()) {
            j = i + 1;
            while (j < boardSb.length() && boardSb.charAt(j) == boardSb.charAt(i)) {
                j++;
            }
            if (j - i == 1) {
                //single color ball
                StringBuilder tmp = new StringBuilder(boardSb);
                int checkColor = tmp.charAt(i) - '0';
                if (handMap[checkColor] >= 2) {
                    handMap[checkColor] -= 2;
                    dfsMinStep(tmp.deleteCharAt(i), handMap, step + 2);
                    handMap[checkColor] += 2;
                }
            } else {
                //two same color ball
                for (int color = 0; color < 5; color++) {
                    if (handMap[color] >= 1) {
                        StringBuilder tmp = new StringBuilder(boardSb);
                        handMap[color]--;
                        dfsMinStep(tmp.insert(i + 1, color), handMap, step + 1);
                        handMap[color]++;
                    }
                }
            }
            i = j;
        }
    }

    private void compress(StringBuilder boardSb) {
        int i = 0;
        int j = 1;
        while (i < boardSb.length()) {
            while (j < boardSb.length() && boardSb.charAt(j) == boardSb.charAt(i)) {
                j++;
            }
            if (j - i > 2) {
                boardSb.delete(i, j);
                j = i + 1;
                while (i > 0 && i < boardSb.length() && boardSb.charAt(i - 1) == boardSb.charAt(i)) {
                    i--;
                }
            } else {
                i = j;
                j++;
            }
        }
    }

    public static void main(String[] args) {
        String board="";
        String hand = "";
        int number = new Solution21().findMinStep(board, hand);
        System.out.println("number = " + number);

                

    }
}